package leetcode.editor.cn;

import java.util.HashSet;
import java.util.Set;

public class _160_IntersectionOfTwoLinkedLists {
    public static void main(String[] args) {
        Solution solution = new _160_IntersectionOfTwoLinkedLists().new Solution();
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    // set
    class Solution1 {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            Set<ListNode> map = new HashSet<>();
            while (headA != null) {
                map.add(headA);
                headA = headA.next;
            }
            while (headB != null) {
                if (map.contains(headB)) {
                    return headB;
                }
                headB = headB.next;
            }
            return null;
        }
    }

    // 双指针
    class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode pA = headA, pB = headB;
            while (pA != pB) {
                pA = pA == null ? headB : pA.next;
                pB = pB == null ? headA : pB.next;
            }
            return pA;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}